package backTrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class combinationSum {
    List<List<Integer>> list =new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //先排序
        //都是正数
        Arrays.sort(candidates);
        if (candidates[0]>target) {
            return list;
        }
        backTrack(candidates, target, 0,new ArrayList<>());

        return list;
    }
    public void backTrack(int[] candidates,int target,int pos,List<Integer> subList){
        if (pos>=candidates.length) {
            return;
        }
        if (target==0) {
            list.add(new ArrayList<>(subList));
        }
        //每个位置可以选或不选
        //判断是否越界，是则提前结束
        //只有哪些没越界的才有选则的权利
        if (candidates[pos]<=target) {
            //因为可以重复选，因此无需mark
            //选
            subList.add(candidates[pos]);
            backTrack(candidates, target-candidates[pos], pos, subList);
            subList.remove(subList.size()-1);
            // 不选
            backTrack(candidates, target, pos+1, subList);
        }else{
            return;
        }
    }
    public static void main(String[] args) {
        
    }
}
